package com.justnow.offer;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/word-break/solution/javacong-bao-li-di-gui-dao-ji-yi-you-hua-by-ngu-6/
 *
 */
public class Solution139 {


    /**
     * 方法一：从头开始遍历s,若遍历到i形成的字符串s[0-i],在字典中wordDict,则只要判断s[i+1, s-s.length()]是否可以拆分为一个或者多个在字典中出翔的单词即可。
     * 考虑到上述情况,选择使用递归的方式来解决这个问题！
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak(String s, List<String> wordDict) {

        HashSet<String> set = new HashSet<>();
        for (String str : wordDict) {
            set.add(str);
        }
        return getResult(s, 0, set);
    }

    private boolean getResult(String s, int start, HashSet<String> set) {
        if (start == s.length()) {
            return true;
        }
        for (int i = start; i < s.length(); i++) {
            if (set.contains(s.substring(start, i + 1))) {
                if (getResult(s, i + 1, set)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 方法二：用memory用来记录,存储重复计算的结果内容
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak2(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>();
        for (String str : wordDict) {
            set.add(str);
        }
        HashMap<Integer, Boolean> memo = new HashMap<>();
        return getResult2(s, 0, set, memo);
    }

    private boolean getResult2(String s, int start, HashSet<String> set, HashMap<Integer, Boolean> memo) {
        if (start == s.length()) {
            return true;
        }
        if (memo.containsKey(start)) {
            return memo.get(start);
        }
        for (int i = start; i < s.length(); i++) {
            if (set.contains(s.substring(start, i + 1))) {
                if (getResult2(s, i + 1, set, memo)) {
                    memo.put(start, true);
                    return true;
                }
            }
        }
        memo.put(start, false);
        return false;
    }

    public static void main(String[] args) {
        String s = "aaaaaaaaaa";
        List<String> list = new ArrayList<>();
        list.add("a");
        list.add("aa");
        list.add("aaa");
        list.add("aaaa");
        Solution139 solution139 = new Solution139();
        boolean b = solution139.wordBreak(s, list);
        System.out.println(b);
    }
}
